package ljl.codetop300;

import commons.WrongAnswer;

import java.util.BitSet;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 删除 k 个数字让剩下的数最小
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 输入：num = "10200", k = 1
 * 输出："200"
 *
 * 思路：看着像是找规律题，不是算法
 * 看第一个例子，肯定不是倒着删，不然 9 就没了
 * 所以是正着删
 * 如果最前面的数后面跟着 0 必须删，因为一下能缩小两位
 * 如果不是 0，得比比，如果后面的数更大，就删后面的
 *
 * 我总结的规律：如果第一个数后面是 0 就删
 * 如果后面的数比前面的大，就删后面的：找到第一个递减序列时停止
 *
 * 俩规律，够吗
 * 算了看答案吧，我时间精力有限
 */
public class _402_remove_k_digits {

    @WrongAnswer
    static class a {
        public String removeKdigits(String num, int k) {
            int len = num.length();
            BitSet mark = new BitSet();
            char[] nums = num.toCharArray();
            while (k > 0) {
                char prev = 0;
                int prevIndex = -1;
                boolean removed = false;
                for (int i = 0; i < len; i++) {
                    if (mark.get(i)) continue;
                    if (prev != 0) {
                        if (nums[i] > prev) {
                            mark.set(i);
                            removed = true;
                            break;
                        }
                    }
                    prev = nums[i];
                    prevIndex = i;
                }
                if (!removed && prev != 0) {
                    mark.set(prevIndex);
                }
                k--;
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++) {
                if (!mark.get(i)) sb.append(nums[i]);
            }
            if (sb.length() == 0) return "0";
            return sb.toString();
        }
    }


    /**
     * 考虑从左往右增量的构造最后的答案：
     * 我们可以用一个栈维护当前的答案序列。
     * 栈中的元素代表截止到当前位置，删除不超过 k 个数字后，所能得到的最小整数。
     * 根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。
     *
     * 因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到：
     * 1. 栈为空
     * 2. 或者新的栈顶元素不大于当前数字
     * 3. 或者我们已经删除了 k 位数字
     */
    static class off {
        public String removeKdigits(String num, int k) {
            Deque<Character> deque = new LinkedList<>();
            int length = num.length();
            for (int i = 0; i < length; ++i) {
                char digit = num.charAt(i);
                while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                    deque.pollLast();
                    k--;
                }
                deque.offerLast(digit);
            }

            // 这个很猥琐，可能本来就是增的，从后往前删除就行
            // 总之很易错
            for (int i = 0; i < k; ++i) {
                deque.pollLast();
            }

            StringBuilder ret = new StringBuilder();
            boolean leadingZero = true;
            while (!deque.isEmpty()) {
                char digit = deque.pollFirst();
                if (leadingZero && digit == '0') {
                    continue;
                }
                leadingZero = false;
                ret.append(digit);
            }
            return ret.length() == 0 ? "0" : ret.toString();
        }
    }

    static class Mine {
        public String removeKdigits(String num, int k) {
            LinkedList<Character> q = new LinkedList<>();
            for (char c : num.toCharArray()) {
                while (!q.isEmpty() && k > 0 && q.peekLast() > c) {
                    q.pollLast();
                    k--;
                }
                q.offerLast(c);
            }
            for (int i = 0; i < k; i++) {
                q.pollLast();
            }
            boolean leadingZero = true;
            StringBuilder sb = new StringBuilder();
            while (!q.isEmpty()) {
                Character c = q.pollFirst();
                if (leadingZero && c == '0') {
                    continue;
                }
                leadingZero = false;
                sb.append(c);
            }
            return sb.length() == 0 ? "0" : sb.toString();
        }
    }
}
